Skip to content
49. 字母异位词分组
概述
给定一个字符串数组，要求将字母异位词分到同一组。两个字符串互为字母异位词，当且仅当它们由完全相同的字符构成，只是排列顺序不同。例如 "eat" 和 "tea" 互为字母异位词，"bat" 则不是。
这个问题的关键在于为每一组等价类找到一个稳定的表示，再借助哈希表完成分组。这里的“等价类”指的是字符组成完全一致的字符串集合；“稳定表示”指的是不管字符顺序如何变化，表示结果都相同。
基本概念
对于任意两个字符串 a 和 b：
- 若
a和b互为字母异位词，则它们的排序结果相同，或字符频次计数相同。 - 排序结果或频次编码可以作为该等价类的标识符（key）。
常用的两种键构造方式如下。
- 排序字符串：将原字符串拆成字符数组，排序，再拼接回字符串。例如
"eat"→"aet"。所有字母异位词都会得到同一个排序结果。 - 字符频次计数编码：统计每个字符的出现次数，按照
字符+次数的格式拼接为键。例如"eat"在 26 个小写字母范围内的编码可能是"a1e1t1"。这比排序省去了排序时的字符比较，但构造编码时需要额外处理频次数组。
工作原理
整体需要做两件事。
- 遍历数组，为每个字符串计算 key：
- 如果使用排序方案，则对字符排序得到 key。
- 如果使用频次计数方案，则扫描字符串填充计数数组，再拼接成 key。
- 将字符串插入哈希表：以 key 为键，值为字符串列表。如果 key 不存在则创建空列表，随后将原字符串追加进去。
遍历结束后，哈希表的值集合即为分组结果。映射结构（Map）的使用保证了同一 key 对应的所有字符串被收集到一起，与遍历顺序无关。
基本用法
排序方案（TypeScript / Node.js）
ts
function groupAnagrams(strs: string[]): string[][] {
const map = new Map<string, string[]>();
for (const str of strs) {
// 将字符串排序为稳定的 key
const key = str.split('').sort().join('');
if (!map.has(key)) {
map.set(key, []);
}
map.get(key)!.push(str);
}
return Array.from(map.values());
}行为解释：
str.split('')将字符串拆解成字符数组（如['e', 'a', 't']）。.sort()按 Unicode 码位排序，得到['a', 'e', 't']。.join('')重新组合为"aet"，作为等价类标识。Map以该标识为键，存储原始字符串的数组。若键不存在则初始化为空数组，再压入原字符串。- 最后通过
Array.from(map.values())取出所有分组，返回二维数组。
频次计数方案（TypeScript）
当字符串中只有 26 个小写字母时，可以用固定大小的计数数组构造键，避免排序开销。
ts
function groupAnagramsByCount(strs: string[]): string[][] {
const map = new Map<string, string[]>();
for (const str of strs) {
const cnt = new Array(26).fill(0);
// 统计字符频次
for (let i = 0; i < str.length; i++) {
cnt[str.charCodeAt(i) - 97]++; // 'a'.charCodeAt(0) === 97
}
// 拼接编码，如 "a1b0...z0"
const key = cnt.map((c, i) => String.fromCharCode(i + 97) + c).join('');
if (!map.has(key)) {
map.set(key, []);
}
map.get(key)!.push(str);
}
return Array.from(map.values());
}行为解释：
cnt是一个长度为 26 的数组，索引 0 对应'a'，索引 25 对应'z'。- 遍历字符串每个字符，将对应位置的计数加一。
- 构造 key 时，将每项转为
"字母+次数"的格式，比如"a1e1t1"，这样所有字母异位词都会得到完全相同的键。 - 如果字符集更大（比如包含 Unicode 字符），这种方式就不如排序方案通用，但仍可通过调整计数数组范围来扩展。
示例
示例 1：常规分组
输入：
ts
["eat", "tea", "tan", "ate", "nat", "bat"]排序后 key 对照：
| 原字符串 | 排序后 key |
|---|---|
| eat | aet |
| tea | aet |
| tan | ant |
| ate | aet |
| nat | ant |
| bat | abt |
输出（分组顺序可能不同）：
ts
[
["eat", "tea", "ate"],
["tan", "nat"],
["bat"]
]示例 2：空字符串
输入：
ts
[""]""排序后仍为""，作为合法 key。- 输出：
[[""]]。
示例 3：单个字符串
输入：
ts
["abc"]- key 为
"abc"，对应的列表只包含一个元素。 - 输出：
[["abc"]]。
示例 4：频次计数方案输出
对于输入 ["eat", "tea", "tan"]，频次计数键可能为：
"eat"→a1b0c0...e1...t1...z0（简写为a1e1t1）"tan"→a1n1t1
分组结果与排序方案一致。
其他语言示例
Java
java
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}排序方案使用 Arrays.sort(char[]) 对字符数组排序，computeIfAbsent 简化了键不存在时的初始化。
Python
python
from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
key = ''.join(sorted(s))
groups[key].append(s)
return list(groups.values())Python 的 sorted(s) 直接返回排序后的字符列表，defaultdict(list) 省去了显式检查键是否存在的步骤。若采用频次计数方案，可使用 tuple 作为键：
python
def group_anagrams_by_count(strs):
groups = defaultdict(list)
for s in strs:
count = [0] * 26
for ch in s:
count[ord(ch) - ord('a')] += 1
groups[tuple(count)].append(s)
return list(groups.values())注意点
- 时间复杂度：排序方案为 O(N·K log K)，其中 N 是字符串数量，K 是最大字符串长度。频次计数方案为 O(N·K)，但常系数略高，且受限于字符集大小。当 K 很小时两种方案均可接受。
- 字符集限制：频次计数方案在小字符集（如 26 个小写字母）下效率更优。若字符串包含任意 Unicode 字符，排序方案更通用。
- 空字符串：
""排序后仍是""，可作为合法的 key，分组逻辑无需特殊处理。 - 输出顺序：
Map的迭代顺序在 ES2015 中为插入顺序，但题目通常不要求分组顺序或组内顺序。实际返回的结果可能因遍历次序而异。 - 单个字符串：应返回
[["abc"]]而非["abc"]——结果始终是二维数组，即使只有一组。
应用
字母异位词分组在多个实际场景中可作为预处理或特征提取的手段。
- 数据去重与聚类：将输入集合中由相同字符组成的字符串归为一组，可快速发现内容相同但排列不同的数据条目。
- 文本特征工程：在自然语言处理中，字母异位词可视为同一特征，减少特征维度。
- 拼写检查与候选词生成：通过构建字母异位词字典，为给定词条提供可能的字母重组形式，辅助拼写纠正。
- 日志相似性分析：将日志中参数位置不同但字符组成相同的记录聚合，便于定位模板。